/**
 * created by lpw
 */
public class TestClass {
    /**
     * 并归实现单链表排序
     * @param args
     */
    public static void main(String[] args) {
        ListNode head=creatNode();
        logNode(head);
        System.out.println("--------------------------分割线--------------------");
        ListNode sort=sortNode(head);
        logNode(sort);
    }

    public static ListNode sortNode(ListNode head){
        if (head==null || head.next ==null){
            return head;
        }
        ListNode middleNode=getMiddle(head);
        ListNode half=middleNode.next;
        //拆分列表
        middleNode.next=null;
        //递归排序
        return merge(sortNode(head),sortNode(half));
    }

    //合并链表
    public static ListNode merge(ListNode a,ListNode b){
        //自己建一个临时的头
        ListNode tempHead=new ListNode(Integer.MIN_VALUE);
        ListNode curr=tempHead;
        while (a !=null && b!=null){
            if (a.val <= b.val){
                curr.next=a;
                a=a.next;
            }else {
                curr.next=b;
                b=b.next;
            }
            curr=curr.next;
        }
        curr.next=(a==null)?b:a;
        return tempHead.next;
    }

    //获取到中间点
    public static ListNode getMiddle(ListNode head){
        if (head==null) return null;
        ListNode slowNode=head;//慢指针
        ListNode fastNode=head;//快指针
        while (fastNode.next!=null && fastNode.next.next!=null){
            slowNode=slowNode.next;
            fastNode=fastNode.next.next;
        }
        return slowNode;
    }

    public static ListNode creatNode(){
        ListNode node1=new ListNode(-1);
        ListNode node2=new ListNode(5);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        ListNode node5=new ListNode(0);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;

        return node1;
    }

    //打印链表
    public static void logNode(ListNode node){
        ListNode temp=node;
        while (temp!=null){
            System.out.println(temp.val);
            temp=temp.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
}